package link;

import array.ListNode;

public class ReorderList143 {
    public void reorderList(ListNode head) {
        ListNode head2 = getMidNode(head);
        head2 = revertList(head2);
        compose(head,head2);
    }

    private void compose(ListNode head, ListNode head2) {
        ListNode node = head;
        while (node!=null){
            if(head2!=null){
                ListNode temp = node.next;
                node.next = head2;
                head2 = head2.next;
                node.next.next = temp;
                node=temp;
            }else {
                return;
            }
        }
    }

    private ListNode revertList(ListNode head2) {
        if(head2==null){
            return head2;
        }
        ListNode pre = null;
        ListNode node = head2;
        while (node.next!=null){
            ListNode temp = node.next ;
            node.next=pre;
            pre = node;
            node=temp;
        }
        node.next=pre;
        return node;
    }

    private ListNode getMidNode(ListNode head) {
        ListNode pre = head;
        ListNode last = head;
        while (pre!=null && pre.next!=null){
            pre = pre.next.next;
            last=last.next;
        }
        ListNode result = last.next;
        last.next =null;
        return result;
    }
}
